package org.example;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 438. 找到字符串中所有字母异位词
 */
public class FindAnagrams {

    /**
     * 官方使用了映射表的数组来存每个字母出现的次数
     */
    public List<Integer> findAnagramsOfficial(String s, String p) {
        if (s == null || p == null || s.length() < p.length()) {
            return List.of();
        }
        List<Integer> ans = new ArrayList<>();
        int[] sCount = new int[26];
        int[] pCount = new int[26];
        for (int i = 0; i < p.length(); i++) {
            pCount[p.charAt(i) - 'a']++;
            sCount[s.charAt(i) - 'a']++;
        }
        if (Arrays.equals(sCount, pCount)) {
            ans.add(0);
        }
        for (int i = 0; i < s.length() - p.length(); i++) {
            sCount[s.charAt(i) - 'a']--;
            sCount[s.charAt(i + p.length()) - 'a']++;
            if (Arrays.equals(sCount, pCount)) {
                ans.add(i + 1);
            }
        }
        return ans;
    }

    /**
     * 自己实现，考虑用map来存每个字母出现的次数
     */
    public List<Integer> findAnagrams(String s, String p) {
        if (s == null || p == null) {
            return List.of();
        }
        char[] charArray = p.toCharArray();
        Map<Character, Integer> map = new HashMap<>();
        for (char c : charArray) {
            if (map.containsKey(c)) {
                map.put(c, map.get(c) + 1);
            } else {
                map.put(c, 1);
            }
        }
        int rk = 0;
        Map<Character, Integer> mapChange = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            if (mapChange.containsKey(s.charAt(i)) && mapChange.get(s.charAt(i)) > 1) {
                mapChange.put(s.charAt(i), mapChange.get(s.charAt(i)) - 1);
            } else {
                mapChange.remove(s.charAt(i));
            }
            while (rk < s.length() && map.containsKey(s.charAt(rk)) && map.get(s.charAt(rk)) > mapChange.get(s.charAt(rk))) {
                rk++;
                mapChange.put(s.charAt(rk), 1);
            }
        }
        return List.of();
    }

    public static void main(String[] args) {
        int[] a = {1, 2, 3, 3};
        int[] b = {3, 2, 3, 1};
        System.out.println(Arrays.equals(a, b));
    }
}
